package lcr;

public class Test0096 {
    public static void main(String[] args) {
        new Solution0096_1().isInterleave("aabcc", "dbbca", "aadbbcbcac");
    }
}

class Solution0096_1 {
    public boolean isInterleave(String s1, String s2, String s3) {
        int l1 = s1.length();
        int l2 = s2.length();
        int l3 = s3.length();
        if (l1 + l2 != l3) return false;
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        char[] chars3 = s3.toCharArray();

        boolean[] pre = new boolean[l2 + 1];
        boolean[] cur = new boolean[l2 + 1];
        pre[0] = true;
        for (int j = 1; j <= l2; j++) pre[j] = pre[j - 1] && chars2[j - 1] == chars3[j - 1];
        for (int i = 0; i < l1; i++) {
            char c1 = chars1[i];
            cur[0]=pre[0]&&c1==chars3[i];
            for (int j = 1; j <= l2; j++) {
                char c2 = chars2[j - 1];
                char c3 = chars3[j + i];
                cur[j]=(pre[j]&&c1==c3)||(cur[j-1]&&c2==c3);
            }
            boolean[] temp = pre;
            pre=cur;
            cur=temp;
        }
        return pre[l2];
    }
}
